class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return intervals;
        }
        // 先排序，然后维护一个最远距离，看是否有重合，有的话更新，没有开始下一组
        Arrays.sort(intervals, (interval1, interval2) -> {
            if (interval1[0] == interval2[0]) {
                return interval1[1] - interval2[1];
            } else {
                return interval1[0] - interval2[0];
            }
        });
        // int a[][] = new int[3][4];
        // a.length == 3 : true
        // a[0].length == 4 : true
        int[][] ansTemp = new int[intervals.length][2];
        int[] curr = intervals[0];
        int idx = 0;
        for (int[] interval : intervals) {
            if (interval[0] <= curr[1]) {
                curr[1] = Math.max(curr[1], interval[1]);
            } else {
                ansTemp[idx++] = curr;
                curr = interval;
            }
        }
        ansTemp[idx++] = curr;
        int[][] ans = new int[idx][2];
        System.arraycopy(ansTemp, 0, ans, 0, idx);
        return ans;
    }
}

/**
[1,3] [2,6]
[2,6] [1,3]
[1,6] [2,3]
[2,3] [1,6]
 */
